package day3;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-12
 * Time:0:14
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 输出超过数组长度一半的数字
 */

public class MoreThanHalfNum_Solution {
    public static void main(String[] args) {
        int[] numbers = {1,2,3,2,2,2,5,4,2};
        //[1,2,3,2,2,2,5,4,2]
        //[3,3,3,3,2,2,2]
        System.out.println(MoreThanHalfNum_Solution(numbers));
    }

    //    public static int MoreThanHalfNum_Solution (int[] numbers) {
//        if (numbers.length == 1){
//            return 1;
//        }
//        int[] num = new int[10];
//
//        int len = numbers.length;
//        for (int i = 0; i < len; i++) {
//            num[numbers[i]]++;
//        }
//        int max = 0;
//        for (int i = 1; i < len; i++) {
//            if (num[i - 1] < num[i]){
//                max = i;
//            }
//        }
//        return numbers[max - 1];
//    }
//    public static int MoreThanHalfNum_Solution(int[] numbers) {
//        //利用map来完成
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < numbers.length; i++) {
//            if (map.containsKey(numbers[i])){
//                map.put(numbers[i], map.get(numbers[i]) + 1);
//            }else {
//                map.put(numbers[i],1);
//            }
//        }
//
//        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
//            if (entry.getValue() > numbers.length / 2){
//                return entry.getKey();
//            }
//        }
//        return -1;
//    }

    /**
     * 众数和非众数
     * 两个数不相等就消去,在最坏情况下:
     * 每消去一个众数和非众数,那么如果存在众数,最后留下的就是众数
     * @param numbers
     * @return
     */

    public static int MoreThanHalfNum_Solution(int[] numbers) {
        //这里注意:numbers == null要放在numbers.length == 0之前判断,因为如果numbers.length == 0先判断的话当是null时会触发空指针异常
        if (numbers == null || numbers.length == 0){
            return 0;
        }
        //代表数-->可能是众数和非众数
        int result = numbers[0];
        //代表数出现的次数但是又不一样,当相同时相加,不同时相减
        int times = 0;

        for (int i = 1; i < numbers.length; i++) {
            if (times != 0){
                if (numbers[i] != result){
                    times--;
                }else {
                    times++;
                }
            }else {
                //更新数
                result = numbers[i];
                //再次计数
                times = 1;
            }
        }
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == result){
                count++;
            }
        }
        return count > (numbers.length/2) ? result : 0;


    }
}
